This invention relates to traffic scheduling and congestion monitoring in an ATM network.
The services that are carried in today""s telecommunications network can be categorised into two main types; real time and non-real time services. The typical examples of these two types are respectively voice telephony and computer data. The two services have very different characteristics and requirements and therefore have traditionally been carried over disjoint network technologies. However to increase flexibility and to decrease costs, there is a major drive by PTTs and network operators to integrate real-time and non-real time services within one homogeneous network. The asynchronous transfer mode (ATM) has been specifically designed to enable this common transport.
A key component of ATM is the adaptation function. This provides the mechanism that adapts the carried service to and from the ATM domain. Several adaptation layers have so far been defined to accommodate the various traffic types that may be transported. For example, ATM Adaptation Layer 1 (AAL1) is designed to adapt constant bit rate services (predominately voice or video) into fixed length ATM cells. A feature of AAL1 is that it enables the timing relationship between the transmitter and receiver to be maintained over the asynchronous network. In contrast, ATM Adaptation Layer 5 (AAL5) has been designed predominantly to support data services. As such it provides a mechanism to segment long data packets into fixed length ATM cells and also provides a mechanism to enable the integrity of the reassembled data packet to be validated after transmission across the network. AAL5 is also being used in certain applications to carry voice services (particularly in computer desktop applications) where AAL5 technology is readily available.
Both AAL1 and AAL5 adapt the carried service into a stream of fixed length ATM cell payloads. However for certain compressed voice services, the length of the standard ATM cell payload (48 bytes) is too large and its use would lead to a large packetisation delay that in turn would affect existing network delay budgets and provide acceptable voice characteristics. To resolve this problem ATM Adaptation :Layer 2 (AAL2) has been defined. AAL2 supports a multiplex of user channels within a single virtual channel connection (VCC). Each user channel is carried in a stream of mini-packets. The length of the mini-packet payload for each channel can be defined according to the packetisation delay that can be tolerated. AAL2 differs from AAL1 and AAL5 in two ways. Firstly it enables a single VCC to support multiple diverse services (a number of simultaneous voice, video and data channels can be multiplexed together to reduce packetisation delay), and secondly it introduces a new switching layer above the ATM layer (i.e. the function of switching a mini-packet connection from one AAL2 VCC to another AAL2 VCC).
To support the full range of telecommunication services operators need to provide these three adaptation layers in an efficient manner. There also needs to be a mechanism to enable the interworking between services carried over different adaptation layers (for example to enable a PSTN user carried via AAL1 to communicate with a desktop voice user hose computer only supports AAL5). To increase flexibility further and to scale networks there is also a requirement to support AAL2 switching. This has introduced problems with the design and efficient operation of ATM schedulers. The purpose of a scheduler is to despatch ATM cells into the network at a controlled rate which minimises congestion and maximises the efficient use of the network resources. The need to handle numerous queues of different traffic classes supported on different ATM adaptation layers has made scheduling a complex and difficult operation.
By way of background, there follows an outline summary of the main ATM traffic classes currently in use.
ATM Traffic Classes
To accommodate the differing behaviours and QoS requirements for a variety of traffic sources, a set of traffic classes is defined in ATM. Each traffic class is designed to describe the characteristics and requirements of a particular type of voice or data service. Five traffic classes have been defined by the ATM Forum [ATMF TM4]-CBR, rt-VBR, nrt-VBR, ABR and UBR.
CBR
The CBR (constant bit rate) traffic class has been designed to support periodic traffic sources that have real-time requirements (i.e. they are delay sensitive). The traffic contract for a CBR connection is entirely specified by its Peak Cell Rate (PCR). The PCR specifies the peak emission rate of ATM cells (and thus implicitly the period between successive cells). All cells within the connection should conform to the PCR. Although the connection is described as CBR, it is perfectly admissible to transmit cells at lower than the PCR, or even to halt emission entirely.
Since the class is real-time, the ATM network commits to delivering cells within a specified delay and jitter bound (CTD and CDV).
rt-VBR
The real-time VBR (variable bit rate) class has been defined to support variable rate real time services (such as certain video streams). A rt-VBR connection is specified in terms of its Sustained Cell Rate (SCR), its Maximum Burst Size (MBS) and its PCR. The SCR defines the mean rate of the connection, the PCR defines the peak rate of any burst and the MBS defines the relationship between the two. Again, as this is a real time connection, the ATM network commits to delivering the service to specified delay and jitter bounds.
nrt-VBR
Specified in an equivalent manner to rt-VBR (PCR, SCR and MBS) this class is provided for the non real-time delivery of delay insensitive variable rate services. There is no delay or jitter commitment made by the ATM network for the delivery of this service.
ABR
In ABR (available bit rate) the source varies its bandwidth usage in accordance to current network congestion which is signalled either implicitly or explicitly through the use of Resource Management (RM) cells.
The key parameters of an ABR connection include:
PCRxe2x80x94peak cell rate
MCRxe2x80x94minimum cell rate (can be zero)
ICRxe2x80x94initial cell rate (start-up rate)
ACRxe2x80x94actual cell rate
CDFxe2x80x94Cell Decrease Factor
CIFxe2x80x94Cell Increase Factor
CRMxe2x80x94missing RM cell count
The connection source transmits two types of cells: data cells and RM cells. The RM cells are transmitted to the receiver where they are looped back to the transmitter. In either direction, each node within the connection can signal its congestion state by inserting information into the RM cell (additionally each intermediate node in the connection can also generate its own RM cells).
The source monitors for the return of the RM cell and changes its connection rate according to the congestion indications contained within it (congestion can be either implicitly or explicitly defined). The RM cells can be sent either as part of the current, contracted rate (set by the ACRxe2x80x94in which case CLP=0) or additionally out-of-rate RM cells can also be sent (CLP=1) at a default rate no greater than 10 per second.
The source uses the following procedure to dictate its behaviour:
On start-up set the ACR to ICR (default PCR)
The first cell sent is always a Forward_RM (which includes an indication of the ACR) at each cell transmission interval send either a:
forward_RM (i.e a RM initiated by the source) if no forward_RM cells have been sent either within a pre-determined time limit (default 100 ms) or a pre-determined number of cell events (default 32 cells)
or send a backward_RM (i.e a RM initiated at the far-end that is being xe2x80x98turned aroundxe2x80x99 by the source) if there is a backward_RM waiting to be sent AND a backward_RM has-not been sent since the last forward_RM was sent OR there is no data cell waiting
or else send a data cell (if one exists)
prior to sending the forward_RM the new ACR rate is computed:
if no forward_RM has been sent since a specified time (the ACR Decrease Time Factor (ADTF)xe2x88x92default value 0.5 seconds) then the ACR=ICR
if no backward_RM has been received from the end-station since the last CRM (default 500 k) forward_RM cells then the ACR=min(ACRxe2x88x92ACR*CDF, MCR) where the CDF is the Cutoff-Decrease-Factorxe2x88x92its default value is {fraction (1/16)}.
when a backward_RM is received (i.e a RM that has looped fully around the connection) the source must adjust its rate
if the backward_RM has a congestion indication (CI=1) then the ACR=min(ACRxe2x88x92ACR*RDF, MCR) RDF is the Rate-Decrease-Factor, default {fraction (1/16)}.
if backward_RM has no increase set (NI=1) then ACR=ACR
else ACR=max(ACR+PCR*RIF, PCR)xe2x80x94where RIF is the Rate-Increase-Factorxe2x88x92default {fraction (1/16)}.
At the receiving station the receiver monitors for RM cells and loops them back. The receiver uses the following procedure:
For received data cells monitor the EFCI (Explicit Forward Congestion Indication) bit
When a forward_RM is received turn-it-around. Generally all fields remain unchanged (except the direction and the BN field which is reset to indicate that the RM cell came from the end station.)
However if the saved EFCI state is set, then the Congestion Indication bit is set, or if internally the receiver is experiencing congestion it can also set the CI/NI bits or define an Explicit Rate
the backward RM can be sent either in-rate or out-rate, generally old RM cells still awaiting scheduling are over-written by newer RM cells
Each switch within the connection must implement one or more of several congestion monitoring techniques (including EFCI marking of data cells; relative rate marking via the CI/NI bits in the RM cells, explicit rate marking via the ER field in the RM, or Virtual Source/Virtual Destination Controlxe2x80x94whereby the control loop is segmented into a number of sections). Switches may also generate there own backward_RM cells (no more than 10/sec)xe2x80x94these are always used to indicate congestion.
UBR
The UBR (unspecified bit rate) service is intended for non real time applications. As its name implies there is no commitment from the network to either the delay or loss bounds for services that utilise this contract. Any congestion control for UBR services must be performed at a higher layer (e.g. application layer) on an end-to-end basis. It is optional for a UBR service whether to specify a PCR. If it is specified then the user may transmit at any rate up to the PCR.
There is a general need to provide a functional partitioning of an adaptation layer technology that enables the interworking requirements to be met with the flexibility to carry a call in any of the standard ATM adaptation layers. Further, a partitioning is required that advantageously enables a number of usable adaptation technology layer modes to be configured from the set of basic building blocks. These modes include trunking between the ATM domain and the legacy carrier domain; interworking between ATM connections (either using the same or a differing adaptation layer) and switching (AAL2). It is further desirable that this partitioning should be scalable such that a range of adaptation capacities can be configured to match the transmission interfaces of the SDH using the set of basic adaptation building blocks. A key requirement of any adaptation layer partitioning is that it optimises buffering apportionment in order to minimise the delay through any system and to minimise the memory and hence cost requirements of any implementation.
As discussed above, a particular problem in designing a network capable of handling these various traffic types and adaptation layers is that of providing, at the adaptation interface to the ATM network, an efficient packet scheduler that can launch assembled packets or cells into the network in a controlled and efficient manner and can meet the various quality of service requirements for those packets or cells.
An object of the invention is to minimise or to overcome the above disadvantage.
A further object of the invention is to provide an improved method and apparatus for ATM packet scheduling.
According to a first aspect of the invention, there is provided a packet scheduler for controlling dispatch of assembled packets at an adaptation interface of an asynchronous (ATM) network, the scheduler being distributed over a common part sublayer device, one or more service specific sublayer devices and an ATM network device so as to be capable of scheduling between said traffic classes in an optimum manner.
According to a further aspect of the invention, there is provided a scheduler for controlling despatch of assembled packets or cells at an adaptation interface of an asynchronous transfer mode (ATM) network supporting a plurality of ATM traffic classes on two or more ATM adaptation layers, the scheduler being distributed over a common part sublayer device, one or more service specific sublayer devices and an ATM network device so as to be capable of scheduling between said traffic classes in an optimum manner
According to a further aspect of the invention, there is provided a traffic scheduler for controlling despatch of assembled packets or cells at an adaptation interface of an synchronous transfer mode (ATM) network supporting a plurality of ATM traffic classes on two or more ATM adaptation layers, the scheduler comprising a distributed hierarchy of individual traffic schedulers one or more at each layer of the hierarchy, wherein each individual scheduler is tuned to respective layer and traffic source characteristics, and wherein an aggregate traffic output at one layer in the hierarchy forms an input to the next layer.
Advantageously, lower-level layers provide feedback to higher layers to control the flow of traffic during periods of congestion. The congestion may be resolved by discarding non-priority packets and by stopping selected individual schedulers.
According to another aspect of the invention, there is provided a method of scheduling despatch of assembled packets or cells at an adaptation interface of an asynchronous transfer mode (ATM) network supporting a plurality of ATM traffic classes on two or more ATM adaptation layers, said method comprising scheduling each said traffic class individually via a traffic scheduler distributed over said adaptation interface so as to be capable of scheduling between said traffic classes in an optimum manner.
Preferably, the scheduler is embodied in software in machine readable form on a storage medium.